package dynamicProgramming.DoubleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/22 21:42
 **/

/**
 * 题目 ：字符串交织
 * 题目详述 ：
 * 给定三个字符串s1、s2、s3，请判断s3能不能由s1和s2交织（交错）组成。
 * 两个字符串 s 和 t 交织的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 提示：a + b 意味着字符串 a 和 b 连接。
 *
 * 提示：
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 */
public class IsInterleaveOptimization {
    /**
     * 思路 ：
     * 使用迭代来判断是否能够字符串s1和字符串s2能否交织成为字符串s3;
     * 需要注意的是，若是要去求解f(i + 1,j + 1)的值，则只需要知道f(i , j + 1) && f(i + 1,j);
     *
     * 状态转移方程 ：
     * 注意 ：假设f(i + 1,j + 1)为长度为i + 1的字符串s1和长度为j + 1的字符串s2能否能够编织成字符串s3（长度为i + j + 2）;
     * （2）若是字符串s3中正在遍历的字符与字符串s1中正在遍历的字符相同的话，即
     * ===》 f(i + 1,j + 1) = f(i,j + 1);
     * f(i + 1,j + 1)是取决于f(i,j + 1),即长度为i的字符串s1和长度为j + 1的字符串s2是否能够编织成字符串s3;
     * （3）若是字符串s3中正在遍历的字符与字符串s2中正在遍历的字符相同的话，即
     * ===》f(i + 1,j + 1) = f(i + 1,j);
     * f(i + 1,j + 1)是取决于f(i + 1,j)，即长度为i + 1的字符串s1和长度为j的字符串s2是否能够编织成字符串s3：
     * （4）若是字符串s3中正在遍历的字符与字符串s1/s2中正在遍历的字符都不相同的话，
     * ===》即，f(i + 1,j + 1) == false;
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        // 假设f(i + 1，j + 1)为字符串s1[0...i]和字符串s2[0...j]是否能够交织成字符串s3[0...(i+j+1)];
        // 若是字符串s1长度 + 字符串s2的长度 != 字符串s3的长度的话，那么字符串s1和字符串s2必然不可能编织成字符串s3;
        if(len1 + len2 != len3){
            return false;
        }
        // 即，使用temp[len2 + 1]的一维数组来存储;
        /**
         * 注意 ：
         * (1)在计算f(i,j)之前，temp[i + 1][j + 1]所存储的是f(i - 1,j)的值;
         * (2)在计算f(i,j)之后，temp[i + 1][j + 1]所存储的就是f(i , j)的值;
         * ===》 通过上述思想，实现temp[i + 1][j + 1]同时存储f(i - 1,j)和f(i , j)两个值;
         */
        // 即，若是要求解f(i + 1,j + 1)的话，则需要知道f(i + 1,j) && f(i , j + 1);
        boolean[] temp = new boolean[len2 + 1];
        // 初始赋值时，temp[0]所指向的是字符串s1和字符串s2皆为空字符串的情况；
        // ===》 字符串s1和字符串s2必然是能够编织成字符串s3（空字符串）;
        temp[0] = true;
        // 初始赋值f(-1,j)情况;(即，字符串s1为空，判断字符串s2是否与字符串s3相等;)
        for(int j = 0; j < len2 ; j++){
            temp[j + 1] = s2.substring(0 , j + 1).equals(s3.substring(0 , j + 1)) ? true : false;
        }
        for(int i = 0; i < len1 ;i++){
            // 此处的temp[0]所存储的值，应该为f(i , -1)情况;(即，字符串s2为空，判断字符串s1是否与字符串s3相等;)
            temp[0] = s1.substring(0 , i + 1).equals(s3.substring(0 , i + 1)) ? true : false;
            // temp[j + 1]所存储的是，f(i , j + 1);
            for(int j = 0; j < len2 ;j++){
                // 要求解f(i + 1,j + 1)的值，所需要知道的是f(i + 1,j)和f(i,j + 1);
                temp[j + 1] = (s1.charAt(i) == s3.charAt(i + j + 1) && temp[j + 1])
                        || (s2.charAt(j) == s3.charAt(i + j + 1) && temp[j]);
                // 在进行temp[j + 1]更新之后，则temp[j + 1]所存储的是f(i + 1,j + 1);
            }
        }
        // 返回值为temp[len2],其所存储的是 长度为len1的字符串s1 和 长度为len2的字符串s2是否能够编织成字符串s3;
        return temp[len2];
    }
}
